package com.structure.traverse;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @Author Tanyu
 * @Date 2020/6/10 14:43
 * @Description 二叉树的遍历
 * @Version 1.0
 */
public class TestTrueDeiTree {

  public static void main(String[] args) {
    TreeNode t1 = new TreeNode(3);
    TreeNode t2 = new TreeNode(9);
    TreeNode t3 = new TreeNode(20);
    TreeNode t4 = new TreeNode(15);
    TreeNode t5 = new TreeNode(7);

    t1.left = t2;
    t1.right = t3;

    t3.left = t4;
    t3.right = t5;

    System.out.println("递归前序遍历：");
    preOrder(t1);
    System.out.println();
    System.out.println("递归中序遍历：");
    midOrder(t1);
    System.out.println();
    System.out.println("递归后序遍历：");
    backOrder(t1);

    System.out.println();
    System.out.println("非递归前序遍历：");
    preOrderStack(t1);

    System.out.println();
    System.out.println("非递归中序遍历：");
    midOrderStack(t1);

    System.out.println();
    System.out.println("非递归后序遍历：");
    backOrderStack(t1);

    System.out.println();
    System.out.println("层次遍历：");
    levelOrder(t1);
  }

  /**
   * 递归实现 根-> 左-> 右 前序遍历
   */
  public static void preOrder(TreeNode root) {
    //结束的条件
    if (root == null) {
      return;
    }
    System.out.print(root.val + " ");
    //使用递归遍历左孩子
    preOrder(root.left);
    //使用递归遍历右孩子
    preOrder(root.right);
  }

  /**
   * 根-->左-->右 非递归前序遍历 1，首先申请一个新的栈，记为stack； 2，声明一个结点treeNode，让其指向node结点；
   * 3，如果treeNode的不为空，将treeNode的值打印，并将treeNode入栈，然后让treeNode指向treeNode的左结点， 4，重复步骤3，直到treenode为空；
   * 5，然后出栈，让treeNode指向treeNode的右孩子 6，重复步骤3，直到stack为空.
   */
  public static void preOrderStack(TreeNode root) {
    //利用栈的特性（先进的后出），用于存储节点数据，一层一层的往上冒
    Stack<TreeNode> stack = new Stack<>();
    //相当于临时的变量，记录当前的所在节点
    TreeNode treeNode = root;

    //两个条件满足一个即可继续执行，退出的条件是当前的节点为null和栈也空了，说明没有数据了
    //栈空了说明冒到了最上一层，最上一层也遍历成了，就空了
    while (treeNode != null || !stack.isEmpty()) {
      //迭代访问节点的左孩子， 并入栈
      //一直遍历最左边的节点
      while (treeNode != null) {
        //先根
        System.out.print(treeNode.val + " ");

        stack.push(treeNode);
        //遍历完根，然后还是遍历最左边的。。如果还有的话，还是遍历最左边的
        treeNode = treeNode.left;
      }
      if (!stack.isEmpty()) {
        //如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
        treeNode = stack.pop();
        treeNode = treeNode.right;
      }
    }
  }

  /**
   * 左-> 根-> 右 中序遍历
   */
  public static void midOrder(TreeNode root) {
    if (root == null) {
      return;
    }
    //使用递归每次都先进行遍历左孩子
    midOrder(root.left);
    System.out.print(root.val + " ");
    //递归遍历右孩子
    midOrder(root.right);
  }

  /**
   * 左-->根-->右 非递归实现中序遍历 申请一个新栈，记为stack，申请一个变量treeNode，初始时令treeNode为头节点；
   * 先把treeNode节点压入栈中，对以treeNode节点为头的整棵子树来说，依次把整棵树的左子树压入栈中，即不断令treeNode=treeNode.leftChild，然后重复步骤2；
   * 不断重复步骤2，直到发现treeNode为空，此时从stack中弹出一个节点记为treeNode，打印node的值，并让treeNode= treeNode.right，然后继续重复步骤2；
   * 当stack为空并且treeNode为空时结束。
   */
  public static void midOrderStack(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
      while (treeNode != null) {
        stack.push(treeNode);
        treeNode = treeNode.left;
      }
      if (!stack.isEmpty()) {
        treeNode = stack.pop();
        System.out.print(treeNode.val + " ");
        treeNode = treeNode.right;
      }
    }
  }


  /**
   * 左-->右-->根 后序遍历 递归实现
   */
  public static void backOrder(TreeNode root) {
    if (root == null) {
      return;
    }
    //使用递归每次都先进行遍历左孩子
    backOrder(root.left);
    //递归遍历右孩子
    backOrder(root.right);
    //根
    System.out.print(root.val + " ");
  }

  /**
   * 左-->右-->根 非递归实现后序遍历
   */
  public static void backOrderStack(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    TreeNode lastVisit = null;   //标记每次遍历最后一次访问的节点
    //节点不为空，结点入栈，并且指向下一个左孩子
    while (treeNode != null || !stack.isEmpty()) {
      while (treeNode != null) {
        stack.push(treeNode);
        treeNode = treeNode.left;
      }
      //栈不为空
      if (!stack.isEmpty()) {
        //出栈
        treeNode = stack.pop();
        /**
         * 这块就是判断treeNode是否有右孩子，
         * 如果没有，则输出treeNode.val，让lastVisit指向treeNode，并让treeNode为空
         * 如果有右孩子，将当前节点继续入栈，treeNode指向它的右孩子,继续重复循环
         */
        if (treeNode.right == null || treeNode.right == lastVisit) {
          System.out.print(treeNode.val + " ");
          lastVisit = treeNode;
          treeNode = null;
        } else {
          stack.push(treeNode);
          treeNode = treeNode.right;
        }
      }
    }
  }

  /**
   * 层次遍历 首先申请一个新的队列，记为queue； 将根结点root压入queue中； 每次从queue中出队，并赋值给root，作为下一次的根，然后打印root.val的值，如果root左孩子不为空，则将左孩子入队；如果root的右孩子不为空，则将右孩子入队；
   * 重复步骤3，直到queue为空。
   */
  public static void levelOrder(TreeNode root) {
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
      root = queue.pop();
      System.out.print(root.val + " ");
      if (root.left != null) {
        queue.add(root.left);
      }
      if (root.right != null) {
        queue.add(root.right);
      }
    }
  }
}
